package com.leetcode.problems018;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Date 2021/11/20 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {

    public List<List<Integer>> fourSum(int[] nums, int target) {
        if(nums == null || nums.length < 4){
            return new ArrayList<>();
        }
        int size = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < size - 3; i = nextNotSampleIndex(i,nums,size - 3)) {
            for (int j =  i + 1; j < size - 2; j = nextNotSampleIndex(j,nums,size - 2)) {
                int l = j + 1;
                int r = size - 1;
                while(l < r){
                    int sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if(sum == target){
                        res.add(Arrays.asList(nums[i] ,nums[j] , nums[l] , nums[r]));
                        l = nextNotSampleIndex(l,nums,r);
                        r = preNotSampleIndex(r,nums,l);
                    }else if(sum < target){
                        l = nextNotSampleIndex(l,nums,r);
                    }else{
                        r = preNotSampleIndex(r,nums,l);
                    }
                }
            }
        }
        return res;
    }

    /**
     * 下一个不相同元素的索引
     * @param currentIndex
     * @param nums
     * @param size
     * @return
     */
    int nextNotSampleIndex(int currentIndex,int[] nums,int size){
        int nextIndex = currentIndex + 1;
        while(nextIndex < size && nums[nextIndex] == nums[currentIndex]){
            nextIndex = nextIndex + 1;
        }
        return nextIndex;
    }


    /**
     * 上一个不相同元素的索引
     * @param currentIndex
     * @param nums
     * @return
     */
    int preNotSampleIndex(int currentIndex,int[] nums,int l){
        int preIndex = currentIndex - 1;
        while(preIndex >= l && nums[preIndex] == nums[currentIndex]){
            preIndex = preIndex  -  1;
        }
        return preIndex;
    }

    public static void main(String[] args) {

        int[] nums = {2,2,2,2,2};

        System.out.println(new Solution().fourSum(nums,8));
    }
}
